//88 归并两个有序数组
/*
给定两个有序数组，把两个数组合并为一个

输入输出样例：
输入是两个数组和它们分别的元素个数 m 和 n。其中第一个数组的长度被延长至 m + n，多出的
n 位被 0 填补。题目要求把第二个数组归并到第一个数组上，不需要开辟额外空间

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: nums1 = [1,2,2,3,5,6]

*/

//
void merge(vector<int> &nums1, int m, vector<int> &nums2, int n)
{
	int pos = m-- + n-- - 1; //pos下标，起始位置为 m + n − 1，最终将目标元素插入pos的位置。每次向前移动 m 或 n 的时候，也要向前移动 pos
	while (m >= 0 && n >= 0)
	{
		nums1[pos--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
	}

	//如果m<n的情况
	while (n >= 0) //
	{
		nums1[pos--] = nums2[n--];
	}
}
